package class07


/*
	给定一个全是小写字母的字符串 str，删除字符串，使得每种字符串只保留一个，
	并让最终结果字符串的字典序最小。
	【举例】：
		str = 'acbc'，删除掉一个'c'，的到 'abc', 是所有结果字符串中字典序最小的
		str = 'dbcacbca'，删除掉第一个'b'，第一个'c'，第二个'c',第二个'a'，得到
		'dabc'，是所有结果字符串中字典序最小的。

	【算法流程】：O(N*K) K 为不重复的字符数量
		1. 先遍历一边字符串，将字符串的数量统计
		2. 循环从左向右遍历，直到有一个字符串的计数为零，此时需要收集之前走过的字符串的最小的字符
		3. 且记录最小字符最先出现的位置，将其收集
		4. 最小字符后面的位置继续循环
*/
func removeDuplicateLetters(s string) string {
	if s == "" {
		return s
	}
	counter := make([]int, 26)
	for i:=0; i<len(s); i++ {
		counter[s[i]-'a']++
	}
	minSIndex := 0
	for i:=0; i<len(s); i++ {
		if s[minSIndex] > s[i] {
			minSIndex = i
		}
		counter[s[i]-'a']--
		if counter[s[i]-'a'] == 0 {
			break
		}
	}
	afterS := ""
	for i:=minSIndex+1; i<len(s); i++ {
		if s[i] != s[minSIndex] {
			afterS += string(s[i])
		}
	}
	return string(s[minSIndex]) + removeDuplicateLetters(afterS)
}